The present invention relates generally to variable length decoders used in data transmission systems, and more particularly, to a variable length decoder for decoding digital video data for high definition television (HDTV).
In digital video data transmission systems, video data is encoded prior to being transmitted to a receiver, which decodes the encoded digital video data. The decoded digital video data is then output to a subsequent signal processing stage. To increase the data throughput and memory efficiency of such systems, statistical compression algorithms are used to compress and encode the digital video data. One such compression algorithm is the Huffman coding algorithm. Compressing the data typically results in data streams segmented into variable length code words rather than fixed length code words. Variable length decoders decode the variable length code words comprising the compressed data stream.
There are several presently available methods for decoding a sequence of variable length code words. The most prevalent methods are the tree searching algorithm and the table look-up technique.
The tree searching algorithm uses a bit-by-bit search through a code tree to find the end and value of each code word in the input bit stream. The coding tree includes leaves of known code words. The decoding process begins at the root of the coding tree and continues bit-by-bit to different branches of the coding tree, depending upon the decoded value of each successive bit in the bit stream. Eventually a leaf is reached and the end of the code word is detected. The code word is then segmented from the rest of the bit stream and the value of the detected code word is looked up and output from the variable length decoder. Decoding a bit stream using the tree searching algorithm is too slow for many high speed applications, since the decoding operation is performed at the bit rate rather than at the symbol rate. In this connection, decoding a bit stream at the bit rate does not satisfy the peak symbol rate requirements of an HDTV decoder.
To increase the data throughput of a variable length decoder, a table look-up decoder was developed, such as the one disclosed in U.S. Pat. No. 5,173,695, issued to Sun et al., the disclosure of which is herein incorporated by reference. The input of the table look-up decoder disclosed in the above-referenced patent is connected to the output of a rate buffer which receives a variable-word-length encoded bit stream at its input and outputs in parallel sequences of bits equal in length to the maximum length code word in the bit stream. These sequences are read into cascaded latches. The cascaded sequences in both latches are input to a barrel shifter which provides from its multi-bit input, a sliding decoding window to a table-lookup decoder. A control signal directly shifts the position of the decoding window of the barrel shifter as each code word is detected.
To detect each code word, the initial bits in the decoding window are compared with code word entries in the table-lookup decoder. When a code word is detected, the corresponding code word length is added to the value of an accumulator with previously accumulated code word lengths to produce the control signal which directly shifts the decoding window by the number of bits in the just decoded word. When all of the bits in the first latch have been decoded, the next bit sequence in the buffer is input to the second latch while the previous bit sequence in the second latch is transferred to the first latch. The decoding window is then shifted to the beginning of the next code word in the undecoded sequence. The shifting of the decoding window and the decoding of the code word can be done in one clock cycle. As a result, the table look-up decoder is capable of decoding one code word per clock cycle regardless of its bit length, thereby dramatically increasing the data throughput of the decoder relative to the previously available tree searching algorithm decoder.
In consumer HDTV applications, however, where the peak symbol rate is about 100 million code words per second, decoding the whole picture at the symbol rate with a single variable length decoder becomes impractical. In HDTV systems, the variable length decoder (VLD) is used to extract an entire picture from a rate buffer within the picture display time. The VLD must decode words in the data stream at the peak symbol rate (PSR), which depends upon the display resolution and the display time. For HDTV systems which use the MPEG ("Moving Pictures Expert Group") protocol, a VLD throughput of 100 million or more code words per second is required. In addition to the technical problems associated with implementing the VLD itself with such throughput, the high-speed VLD interface with the large capacity rate buffer is quite expensive with the currently available memory technology. The problem becomes more severe if price is an issue, since faster and more expensive memory devices such as static random access memories (SRAMs) and synchronous dynamic random access memories (SDRAMs) must be used, rather than slower and cheaper memory devices such as asynchronous DRAMs. Of course, the price of the memory is a particularly important consideration for a consumer product, such as an HDTV set.
In current implementations, HDTV systems are normally partitioned into multiple processing paths, using multiple VLDs to decode different portions of the picture in parallel. In such implementations, the VLD is one of the major bottlenecks. Because each partition of the picture may contain almost all of the picture information, multiple dedicated ping-pong buffers are required between all of the VLDs and the rate buffer, thereby dramatically increasing the amount of bit stream memory required for the system. For example, a partitioned decoding system having eight parallel VLDs requires eight ping-pong buffers, each one of the ping-pong buffers being twice the size of the rate buffer, thereby increasing the amount of required buffer memory by a factor of sixteen over a system having a single VLD.
Based on the above and foregoing, it can be appreciated that there presently exists a need in the art for a variable length decoder which overcomes the above-discussed drawbacks and shortcomings of the presently available technology, and which can be used to implement a single VLD HDTV decoder, rather than a partitioned HDTV decoder. More particularly, there presently exists a need in the art for a variable length decoder having a data throughput which is adequate for processing digital video data.
The present invention fulfills this need in the art by providing a variable length decoder having a word length computation loop which is implemented in a one-hot architecture. The one-hot architecture of the word length computation loop of the variable length decoder of the present invention significantly reduces the propagation delay through the word length computation loop relative to the word length computation loop used in the conventional variable length decoders, such as the one disclosed in the above-referenced Sun et al. patent, and thereby greatly accelerates the word length computation loop, thus facilitating greater throughput. In this regard, the one-hot word length computation loop of the present invention eliminates the layers of logic gates required in the conventional word length computation loop, which includes a wide-barrel shifter, a conventional word length decoder with large Huffman look-up tables, and an adder-accumulator.
With the one-hot architecture of the word length computation loop of a preferred embodiment of the present invention, the wide-barrel shifter is replaced by a "one-hot" bit stream barrel shifter matrix, the conventional word length decoder is replaced by a "one-hot" word length decoder, and the adder is replaced by a "one-hot" ring barrel shifter matrix and "one-hot" overflow barrel shifter matrix. Alternatively, significant acceleration of the word length computation loop can be achieved even if conventional barrel shifters are used instead of the "one-hot" barrel shifter matrices.